# 在一系列的数据元素中，可能是以各种数据结构的形式去存储的
# 通过指定的方法，找出给定关键字相同数据元素的过程

# 在线性表中进行查找，在一个基于数组的方式去存储数据的时候如何才能提高我们查找数据的效率

# 输入：目标的列表，以及你待查找的元素
# 输出：元素的角标（index），如果说没找到返回 None 或者 -1
# python：


# 1.单次计算的耗时比我们低
# 2.在我们设定了指定的计算方法后，计算机一定能按照我们设定的方法去做，不会干活打折扣

# 顺序查找：从列表的第一个元素开始，顺序进行搜索，直到，找到目标的最后一个元素为止


def linear_search(li: list, val) -> int:
    """
    线性查找，如果有多个重复值只返回第一个
    :param li:
    :param val:
    :return:
    """
    for i in range(len(li) - 1):
        if li[i] == val:
            return i
    return -1


def linear_search_v2(li: list, val) -> list:
    """
    线性查找，如果有多个重复值，则都返回
    :param li:
    :param val:
    :return:
    """
    index_list = []
    for i in range(len(li) - 1):
        if li[i] == val:
            index_list.append(i)
    return index_list


# 线性查找的时间复杂度一定是 O(n)
